package com.wc.alorithm.string.KMP;

/**
 * @Author congege
 * @Description KMP 算法
 * @Date Created in 2023/11/30-14:17
 */
public class Main {
    /**
     * 字符串匹配单一模式
     *
     * @param str 主串
     * @param sub 子串
     * @param pos 在主串当中的位置
     * @return 返回查找到的第一个子串位置，若是未找到就返回 -1
     */
    public static int kmp(String str, String sub, int pos) {
        // 为空的时候返回-1
        if (str == null || sub == null) {
            return -1;
        }
        int lenStr = str.length();
        int lenSub = sub.length();
        // 为空字符串时候返回-1
        if (lenStr == 0 || lenSub == 0) {
            return -1;
        }
        // 当位置不合法的时候返回-1
        if (pos < 0 || pos >= lenStr) {
            return -1;
        }
        int i = pos;
        int j = 0;
        int[] next = new int[lenSub];
        int[] nextVal = new int[lenSub];
        getNext(sub, next);
        getNextVal(sub, next, nextVal);
        while (i < lenStr && j < lenSub) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = nextVal[j];
            }
        }
        // 当匹配到了第一个得坐标
        if (j >= lenSub) {
            return i - j;
        }

        return -1;
    }

    /**
     * 计算next数组
     *
     * @param sub  字串
     * @param next next数组
     */
    public static void getNext(String sub, int[] next) {
        int lenSub = next.length;
        next[0] = -1;
        if (lenSub >= 2) {
            next[1] = 0;
        }
        int i = 2;
        int k;
        while (i < lenSub) {
            // 前一个位置的下标
            k = next[i - 1];
            // 如果不相等，就一直往前面找，找到相等为止，或者没有相等的就找到-1;
            while (k != -1 && sub.charAt(i - 1) != sub.charAt(k)) {
                k = next[k];
            }
            next[i] = k + 1;
            i++;
        }
    }

    public static void getNextVal(String sub, int[] next, int[] nextVal) {
        nextVal[0] = next[0];
        for (int i = 1; i < next.length; i++) {
            if (sub.charAt(next[i]) == sub.charAt(i)) {
                nextVal[i] = nextVal[next[i]];
            } else {
                nextVal[i] = next[i];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(kmp("ababcab2cdabcde", "ab2c", 0));
    }
}
